package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/'>填充每个节点的下一个右侧节点指针(Populating Next Right Pointers in Each Node)</a>
 * <p>
 * 给定一个<b>完美二叉树</b> ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 * <pre>
 *  struct Node {
 *      int val;
 *      Node *left;
 *      Node *right;
 *      Node *next;
 *  }
 * </pre>
 * </p>
 * <p>填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。</p>
 * <p>初始状态下，所有 next 指针都被设置为 NULL。</p>
 * <p>
 * <pre><a href='https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/'>查看示例</a></pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中节点的数量在 [0, 2^12 - 1] 范围内</li>
 *      <li>-1000 <= node.val <= 1000</li>
 *  </ul>
 * </p>
 * <b>进阶：</b>
 * <ui>
 * <li>你只能使用常量级额外空间。</li>
 * <li>使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。</li>
 * </ui>
 *
 * @author c2b
 * @since 2023/4/27 18:29
 */
public class LC0116PopulatingNextRightPointersInEachNode_I_M {

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        // 当前层最左节点(从第一层开始->父节点)
        Node currLevelLeftmostNode = root;
        while (currLevelLeftmostNode.left != null) {
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node currNode = currLevelLeftmostNode;
            while (currNode != null) {
                // 第一种情况是连接同一个父节点的两个子节点。它们可以通过同一个节点直接访问到
                currNode.left.next = currNode.right;
                // 第二种情况在不同父亲的子节点之间建立连接，这种情况不能直接连接。
                if (currNode.next != null) {
                    currNode.right.next = currNode.next.left;
                }
                // 进入当前层的下一个节点
                currNode = currNode.next;
            }
            // 去下一层的最左节点
            currLevelLeftmostNode = currLevelLeftmostNode.left;
        }
        return root;
    }

    public Node connect2(Node root) {
        // 首先判断根节点root是否为空，如果为空，则直接返回null。
        if (root == null) {
            return null;
        }
        // 创建一个队列queue，并将根节点root加入队列。
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        // 定义两个指针变量currLevelLastNode和lastLevelLastNode，分别表示当前层的最后一个节点和下一层的最后一个节点。
        // 初始时，currLevelLastNode指向根节点root，lastLevelLastNode为null。
        Node currLevelLastNode = root;
        Node lastLevelLastNode = null;
        // 进入一个循环，循环条件是队列不为空。
        while (!queue.isEmpty()) {
            // 在循环中，从队列中取出一个节点currNode。
            Node currNode = queue.poll();
            // 首先判断当前节点的左子节点和右子节点是否存在，如果存在，则将它们加入队列，并更新lastLevelLastNode为最后加入的节点。
            if (currNode.left != null) {
                queue.offer(currNode.left);
                lastLevelLastNode = currNode.left;
            }
            if (currNode.right != null) {
                queue.offer(currNode.right);
                lastLevelLastNode = currNode.right;
            }
            // 接下来，判断当前节点是否为当前层的最后一个节点（即currNode == currLevelLastNode）。
            if (currNode == currLevelLastNode) {
                // 如果是最后一个节点，说明当前层的节点已经处理完毕，将当前节点的next指针指向null，然后更新currLevelLastNode为lastLevelLastNode，表示进入下一层。
                // 同时，将lastLevelLastNode重置为null，以便在下一层中更新为新加入的节点的最后一个节点。
                currNode.next = null;
                currLevelLastNode = lastLevelLastNode;
                lastLevelLastNode = null;
            } else {
                // 如果不是最后一个节点，将当前节点的next指针指向队列中的下一个节点（即queue.peek()）。
                currNode.next = queue.peek();
            }
        }
        return root;
    }

    // Definition for a Node.
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        LC0116PopulatingNextRightPointersInEachNode_I_M lc0116Connect_m = new LC0116PopulatingNextRightPointersInEachNode_I_M();
        Node connect = lc0116Connect_m.connect(node1);
    }
}
